#ifndef __DOUBLELINKLIST_H_
#define __DOUBLELINKLIST_H_

#include "DoubleLinkList.h"
#include <iostream>
template<typename T>
class DoubleLinkList
{
public:


    DoubleLinkList();
    ~DoubleLinkList();

    //插入
    void InsertTail(const T& element); //尾插

    //删除
    void RemoveByIndex(int index);//按位置删

    int Size()
    {
        return size;
    }

    T* Back()
    {
        return &tail->data;
    }

    T* Head()
    {
        return &head->next->data;
    }
    void show();
private:
    struct Node
    {
        Node(const T& data):data(data),prev(nullptr),next(nullptr){}
        T data;
        Node* next;//后置指针
        Node* prev;//前置指针
    };
    Node* head;
    Node* tail;
    int size;

};



#endif

template<typename T>
DoubleLinkList<T>::DoubleLinkList() : size(0)
{
    head = new Node(0);
    tail = head;
}

template<typename T>
DoubleLinkList<T>::DoubleLinkList::~DoubleLinkList()
{
    while (head != nullptr)
    {
        Node *nextNode = head->next; // 记下下一个结点
        delete head;
        head = nextNode; // 结点往后走
    }
}

template<typename T>
void DoubleLinkList<T>::InsertTail(const T &element)
{
    Node *newNode = new Node(element);
    tail->next = newNode;
    newNode->prev = tail;
    tail = newNode;
    size++;
}


template<typename T>
void DoubleLinkList<T>::RemoveByIndex(int index)
{
    if (index < 0 || index >= size)
    {
        std::cerr << "非法删除位置!\n";
        return;
    }

    Node *freeNode = nullptr;

    if (index == 0)
    {
        freeNode = head->next;       // 头节点的下一个节点
        head->next = freeNode->next; // 头节点的 next 指向删除节点的 next
        if (freeNode->next != nullptr)
        {
            freeNode->next->prev = head; // 删除节点的 next 的 prev 指向头节点
        }
        else
        {
            tail = head; // 如果删除的是唯一节点，更新 tail 为 head
        }
    }

    else if (index == size - 1)
    {
        freeNode = tail;      // 指向尾节点
        tail = tail->prev;    // 更新尾节点为前一个节点
        tail->next = nullptr; // 新尾节点的 next 设为 nullptr
    }

    // 删除中间节点
    else
    {
        Node *travelPoint = head->next;
        for (int i = 0; i < index; ++i)
        {
            travelPoint = travelPoint->next;
        }
        freeNode = travelPoint;
        travelPoint->prev->next = travelPoint->next; // 前一个节点的 next 指向要删除节点的 next
        travelPoint->next->prev = travelPoint->prev; // 后一个节点的 prev 指向要删除节点的 prev
    }

    delete freeNode;
    size--;
}


